Educational Codeforces Round 106 (Div. 2) C Minimum Grid Path
問題の条件を一旦奇数番目の要素と偶数番目の要素に分けて考える. するとそれぞれの和が$ nであって問題文の式が最小になるように値を定めればよく, これはある要素に集中させ, それより前の要素は$ 1に, それより後の要素は$ 0にし, そのコストを累積和を用いて求めその最小値を求めることで対応できる. しかしこれを分けたまま行うと上手くいかない. そこでそのままの配列に対して順次この計算を行っていくことにより解くことができる.